﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0213_GetKthMagicNumber : IAlgorithm
    {
        // 面试题 17.09. 第 k 个数

        /*
        有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。
        注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
        */

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
        }

        // 算法
        // 1，3，5，7，9，15，21，25，27，35，45，49，
        public int GetKthMagicNumber(int k)
        {
            int[] dp = new int[k + 1];
            dp[1] = 1;
            int p3 = 1, p5 = 1, p7 = 1;
            for (int i = 2; i <= k; i++)
            {
                int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
                dp[i] = Math.Min(Math.Min(num3, num5), num7);
                if (dp[i] == num3) p3++;
                if (dp[i] == num5) p5++;
                if (dp[i] == num7) p7++;
            }
            return dp[k];
        }
    }
}
